struct EBCC
{
    int n;
    vector<pair<int, int>> e;
    vector<vector<int>> adj;
    vector<int> stk, dfn, low, id;
    int now, cnt;
    EBCC() {}
    EBCC(int n)
    {
        this->n = n;
        adj.assign(n + 1, {});
        dfn.assign(n + 1, -1);
        low.resize(n + 1);
        id.assign(n + 1, -1);
        now = cnt = 0;
        stk.clear();
    }
    void add(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs(int u, int p)
    {
        dfn[u] = low[u] = now++;
        stk.push_back(u);
        for (auto v : adj[u])
        {
            if (v == p)
                continue;
            if (dfn[v] == -1)
            {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (dfn[u] < low[v])
                    e.emplace_back(u, v);
            }
            else if (id[v] == -1 && dfn[v] < dfn[u])
            {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u])
        {
            int y;
            cnt++;
            do
            {
                y = stk.back();
                stk.pop_back();
                id[y] = cnt;
            } while (y != u);
        }
    }
    vector<int> work()
    {
        dfs(1, -1);
        return id;
    }
    struct G
    {
        int n;
        vector<pair<int, int>> edges;
        vector<int> siz;
        vector<int> cnte;
    };
    G rebuild()
    {
        G g;
        g.n = cnt;
        g.siz.resize(cnt + 1);
        g.cnte.resize(cnt + 1);
        for (int i = 1; i <= n; i++)
        {
            g.siz[id[i]]++;
            for (int j : adj[i])
            {
                if (id[i] <= id[j])
                {
                    g.edges.emplace_back(id[i], id[j]);
                }
                else if (i < j)
                {
                    g.cnte[id[i]]++;
                }
            }
        }
        return g;
    }
};